package com.spring.schooltest.test;

import java.util.LinkedList;

public class LRU {
	public void L(int[] seq,int pages){
		int page_break = 0;// 断页次数
		// 储存容器，LinkedList底层通过链表来实现，随着元素的增加不断向链表的后端增加节点
		LinkedList<Integer> list = new LinkedList<Integer>();
		// 通过for循环来遍历seq数组
		for (int i = 0; i < seq.length; i++) {
			if (list.contains(seq[i])) {// 如果即将访问的序列在物理块中，重新记录其访问状态
				int flag = list.indexOf(seq[i]);// 标记已经存在的序列的下标
				list.remove(flag);// 删除这个元素
				list.addLast(seq[i]);// 在末尾重新添加它
			} else {// 如果即将访问的序列不在物理块中，添加到物理块中；如果满了，找到最久不被访问的序列，并删除替换
				if(list.size()!=pages) {
					list.addLast(seq[i]);// 该方法表示将指定的元素追加到此列表的末尾
					page_break++;//访问序列不存在，断页加一
				}else {
					list.removeFirst();// 删除第一个元素
					list.addLast(seq[i]);// 追加最后一个新元素
					page_break++;// 置换，断页加一
				}
			}
		}
		// 输出结果
		System.out.println("断页次数：" + page_break + "\n断页中断率：" + page_break * 1.0 / seq.length);
	}
}
